#include <iostream>
#include <map>
#include <random>

using namespace std;

class RandomizedSet {
  /*
    map insert and remove
    get random use cpp libs
   */
public:
  map<int, bool> m_set;
  RandomizedSet() {}

  bool insert(int val) {
    map<int, bool>::iterator find = m_set.find(val);
    if (find != m_set.end()) {
      return false;
    }
    m_set.insert(map<int, bool>::value_type(val, true));
    return true;
  }

  bool remove(int val) {
    map<int, bool>::iterator find = m_set.find(val);
    if (find == m_set.end()) {
      return false;
    }
    m_set.erase(find);

    return true;
  }

  int getRandom() {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, m_set.size() - 1);

    int randomIndex = dis(gen);

    map<int, bool>::iterator it = m_set.begin();
    std::advance(it, randomIndex);

    return it->first;
  }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

int main() {
  RandomizedSet *obj = new RandomizedSet();

  int val = 10;

  bool param_1 = obj->insert(val);

  val = 9;
  bool param_2 = obj->remove(val);
  int param_3 = obj->getRandom();
  cout << param_3 << endl;
  return 0;
}
